Queue একটি FIFO (First In, First Out) ডাটা স্ট্রাকচার, যেখানে প্রথমে আসা উপাদানটি প্রথমে বের হয়ে যায়। এটি এমন কিছু সমস্যার সমাধান করতে সাহায্য করে যেখানে এলিমেন্টগুলো একে একে প্রসেস করা প্রয়োজন, যেমন Breadth-First Search (BFS) এবং Print Jobs।
এই গাইডে আমরা Queue এর ব্যবহার কিভাবে Breadth-First Search (BFS) এবং Print Jobs মডেল করতে সাহায্য করে তা দেখবো।
1. Queue এর মৌলিক ধারণা
Queue একটি ডাটা স্ট্রাকচার, যা দুটি মৌলিক অপারেশন সমর্থন করে:
- enqueue: একটি উপাদান কোডের শেষে যোগ করা।
- dequeue: কোডের শুরুর থেকে উপাদানটি বের করা।
Queue সাধারণত দুইটি জায়গায় কাজ করে:
- front: প্রথম উপাদান যেখানে থাকে।
- rear: শেষ উপাদান যেখানে যোগ করা হয়।
import java.util.LinkedList;
import java.util.Queue;
public class QueueExample {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
// Enqueue
queue.add(1);
queue.add(2);
queue.add(3);
// Dequeue
System.out.println("Dequeued: " + queue.poll()); // Output: 1
// Peek at the front element
System.out.println("Front element: " + queue.peek()); // Output: 2
}
}
এখানে, LinkedList ব্যবহার করা হয়েছে Queue ইন্টারফেসের জন্য। add() মেথড দিয়ে ইনকিউ করতে এবং poll() মেথড দিয়ে ডিকিউ করতে হয়। peek() মেথড দ্বারা প্রথম উপাদান দেখতে পারি।
2. Breadth-First Search (BFS) with Queue
Breadth-First Search (BFS) একটি গ্রাফ ট্রাভার্সাল অ্যালগরিদম যা Queue ব্যবহার করে। এটি প্রথমে বর্তমান নোডের পাশের নোডগুলো একে একে পরিদর্শন করে। Queue এর সাহায্যে, BFS একটি স্তরের সব নোড পরিদর্শন করে এবং পরবর্তী স্তরের নোডগুলোকে প্রসেস করে।
2.1. BFS Implementation using Queue
import java.util.*;
public class BFS {
// Graph representation using adjacency list
private Map<Integer, List<Integer>> adjList;
public BFS() {
adjList = new HashMap<>();
}
// Add edges to the graph
public void addEdge(int u, int v) {
adjList.putIfAbsent(u, new ArrayList<>());
adjList.putIfAbsent(v, new ArrayList<>());
adjList.get(u).add(v);
adjList.get(v).add(u); // For undirected graph
}
// BFS traversal
public void bfs(int start) {
Queue<Integer> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
visited.add(start);
queue.add(start);
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " ");
// Traverse the adjacent nodes
for (int neighbor : adjList.get(node)) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.add(neighbor);
}
}
}
}
public static void main(String[] args) {
BFS graph = new BFS();
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
graph.addEdge(2, 5);
graph.addEdge(3, 6);
System.out.print("BFS traversal starting from node 1: ");
graph.bfs(1); // Output: 1 2 3 4 5 6
}
}
2.2. Explanation of BFS using Queue:
- প্রথমে স্টার্ট নোডকে visited সেটে যোগ করা হয় এবং queue এ যুক্ত করা হয়।
- তারপর, queue এর মধ্যে থেকে একে একে নোড বের করা হয় এবং তার প্রতিবেশী নোডগুলোকে visited চেক করে queue তে যোগ করা হয়।
- এভাবে, BFS পুরো গ্রাফকে স্তরানুসারে পরিদর্শন করে।
Queue ব্যবহার করার কারণে BFS অ্যালগরিদম FIFO নীতিতে কাজ করে, অর্থাৎ প্রথমে যোগ হওয়া নোডটি আগে পরিদর্শন করা হয়।
3. Print Jobs with Queue
Print Jobs মডেল করার জন্যও Queue ব্যবহার করা যেতে পারে। ধরুন, একটি প্রিন্টার সার্ভার আছে যেখানে অনেক প্রিন্ট জব পেন্ডিং রয়েছে। Queue-এর সাহায্যে আমরা এগুলিকে প্রসেস করতে পারি, প্রথমে যে প্রিন্ট জব এসেছে সেটি আগে প্রিন্ট হবে।
3.1. Print Jobs Simulation Using Queue
import java.util.LinkedList;
import java.util.Queue;
public class PrintJobQueue {
static class PrintJob {
String document;
int pages;
PrintJob(String document, int pages) {
this.document = document;
this.pages = pages;
}
}
public static void main(String[] args) {
// Creating a Queue for print jobs
Queue<PrintJob> printQueue = new LinkedList<>();
// Adding print jobs to the queue
printQueue.add(new PrintJob("Document1.pdf", 10));
printQueue.add(new PrintJob("Document2.pdf", 15));
printQueue.add(new PrintJob("Document3.pdf", 5));
// Process each print job in the queue
while (!printQueue.isEmpty()) {
PrintJob job = printQueue.poll(); // Get the next print job
System.out.println("Printing: " + job.document + " (" + job.pages + " pages)");
// Simulate printing process
}
}
}
3.2. Explanation:
- PrintJob ক্লাসে একটি ডকুমেন্ট এবং তার পেজ সংখ্যা থাকে।
- Queue ব্যবহার করে, আমরা প্রিন্ট জবগুলো যুক্ত করি।
- poll() মেথড ব্যবহার করে প্রথম প্রিন্ট জবটি বের করা হয় এবং প্রিন্ট করা হয়।
এখানে Queue FIFO পদ্ধতিতে কাজ করে, যেখানে প্রথমে আসা প্রিন্ট জবটি আগে প্রিন্ট হবে।
4. Complex Example: Combining BFS and Print Jobs
ধরা যাক, আমরা একটি পরিস্থিতি তৈরি করতে চাই যেখানে গ্রাফের নোডগুলি প্রিন্ট জব হিসেবে ব্যবহৃত হবে এবং BFS অ্যালগরিদমের মাধ্যমে তাদের প্রক্রিয়া করা হবে।
4.1. BFS with Print Jobs
import java.util.*;
public class BFSWithPrintJobs {
static class PrintJob {
String document;
int pages;
PrintJob(String document, int pages) {
this.document = document;
this.pages = pages;
}
@Override
public String toString() {
return document + " (" + pages + " pages)";
}
}
static class Graph {
private Map<Integer, List<Integer>> adjList = new HashMap<>();
// Add an edge to the graph
public void addEdge(int u, int v) {
adjList.putIfAbsent(u, new ArrayList<>());
adjList.putIfAbsent(v, new ArrayList<>());
adjList.get(u).add(v);
adjList.get(v).add(u);
}
// BFS with Print Job Simulation
public void bfsWithPrintJobs(int start) {
Queue<Integer> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
Queue<PrintJob> printQueue = new LinkedList<>();
visited.add(start);
queue.add(start);
// Simulate adding print jobs for each node
printQueue.add(new PrintJob("Print Job for Node " + start, 10));
while (!queue.isEmpty()) {
int node = queue.poll();
PrintJob currentJob = printQueue.poll();
System.out.println("Processing print job: " + currentJob);
// Traverse adjacent nodes and add print jobs
for (int neighbor : adjList.get(node)) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.add(neighbor);
printQueue.add(new PrintJob("Print Job for Node " + neighbor, 5)); // Assigning 5 pages for simplicity
}
}
}
}
}
public static void main(String[] args) {
Graph graph = new Graph();
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
graph.addEdge(3, 5);
System.out.println("BFS with Print Jobs Simulation:");
graph.bfsWithPrintJobs(1);
}
}
4.2. Explanation:
- এখানে, আমরা BFS ট্রাভার্সাল ব্যবহার করেছি এবং প্রতিটি নোডের জন্য PrintJob তৈরি করেছি।
- PrintJob একে একে প্রিন্ট হচ্ছে, এবং নোডের পাশের নোডগুলোর জন্য নতুন প্রিন্ট জব তৈরি হচ্ছে।
সারাংশ
Queue একটি অত্যন্ত শক্তিশালী ডাটা স্ট্রাকচার যা BFS (Breadth-First Search) এবং Print Jobs মডেলিং এর মতো বিভিন্ন কাজে ব্যবহৃত হয়। BFS গ্রাফ ট্রাভার্সাল এবং Print Jobs-এ কুয়েরি পরিচালনা করতে FIFO প্রক্রিয়ায় কাজ করে। এই প্রোগ্রামগুলি কিভাবে Queue ব্যবহার করে ডাটা প্রসেস এবং প্রিন্ট জবসমূহ পরিচালনা করা যায় তা দেখায়।
Key Takeaways:
- Queue হল FIFO ডাটা স্ট্রাকচার।
- BFS গ্রাফ ট্রাভার্সাল করতে Queue ব্যবহার করা হয়।
- Print Jobs মডেল করতে Queue ব্যবহৃত হয় যেখানে প্রথমে আসা জবটি প্রথমে প্রিন্ট করা হয়।
Read more
